// 二叉树的遍历 https://blog.csdn.net/rxbook/article/details/130969288
package main

import "fmt"

type BinaryTree struct {
	Value     int
	LeftNode  *BinaryTree
	RightNode *BinaryTree
}

// 前序遍历: 根节点 ---> 左子树 ---> 右子树
func preOrder(node *BinaryTree) {
	if node == nil {
		return
	}
	fmt.Printf("%v ", node.Value)
	preOrder(node.LeftNode)
	preOrder(node.RightNode)
}

// 中序遍历: 左子树---> 根节点 ---> 右子树
func inOrder(node *BinaryTree) {
	if node == nil {
		return
	}
	inOrder(node.LeftNode)
	fmt.Printf("%v ", node.Value)
	inOrder(node.RightNode)
}

// 后序遍历: 左子树 ---> 右子树 ---> 根节点
func tailOrder(node *BinaryTree) {
	if node == nil {
		return
	}
	tailOrder(node.LeftNode)
	tailOrder(node.RightNode)
	fmt.Printf("%v ", node.Value)
}

// 层序遍历,从root节点一层一层的遍历
func levelOrder(rootNode *BinaryTree) {
	if rootNode == nil {
		return
	}
	var nodeSlice []*BinaryTree // 封装一个slice
	nodeSlice = append(nodeSlice, rootNode)
	recursion(nodeSlice) //递归遍历
}

// 递归遍历核心
func recursion(nodeSlice []*BinaryTree) {
	if len(nodeSlice) == 0 { // 如果当前层级slice为空，则结束遍历
		return
	}
	var nextSlice []*BinaryTree           // 创建新的节点slice，存储下一层需要遍历的node
	for i := 0; i < len(nodeSlice); i++ { //遍历当前nodeSlice
		node := nodeSlice[i]          //取出要遍历的node
		fmt.Printf("%v ", node.Value) //输出当前node的值
		if node.LeftNode != nil {     //当前node左子节点append到下一层nodeSlice中
			nextSlice = append(nextSlice, node.LeftNode)
		}
		if node.RightNode != nil { //当前node右子节点append到下一层nodeSlice中
			nextSlice = append(nextSlice, node.RightNode)
		}
	}
	recursion(nextSlice) //递归遍历下一层的nodeSlice
}

func main() {
	//测试
	/*
	       1
	      / \
	     2   3
	    / \   \
	   4   5   6
	*/
	var rootNode = &BinaryTree{
		Value: 1,
		LeftNode: &BinaryTree{
			Value: 2,
			LeftNode: &BinaryTree{
				Value: 4,
			},
			RightNode: &BinaryTree{
				Value: 5,
			},
		},
		RightNode: &BinaryTree{
			Value: 3,
			RightNode: &BinaryTree{
				Value: 6,
			},
		},
	}

	//前序遍历
	preOrder(rootNode) //1 2 4 5 3 6
	println()

	//中序遍历
	inOrder(rootNode) //4 2 5 1 3 6
	println()

	//后序遍历
	tailOrder(rootNode) //4 5 2 6 3 1
	println()

	//层序遍历
	levelOrder(rootNode) //1 2 3 4 5 6
	println()

}
